package Aleehot100;

/**
 * ClassName: c046
 * Package: Aleehot100
 * Description: 114. 二叉树展开为链表 空间要求O(1)
 *
 * @Author BCXJ
 * @Create 2025/7/16 08:39
 * @Version 1.0
 * @Since 1.0
 */
public class c046 {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        node1.left = node2;
        node1.right = node5;
        node2.left = node3;
        node2.right = node4;
        node5.right = node6;
        flatten(node1);
    }
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    /**
     * 很妙的解法哦，这是
     * @param root
     */
    public static void flatten(TreeNode root) {
        TreeNode cur = root, next, pre = null;
        while(cur != null) {
            if(cur.left != null) {
                next = cur.left;
                while(next != null) {
                    pre = next;
                    next = next.right;
                }
                next = cur.left ;// 归位
                cur.left = null;
                pre.right = cur.right;
                cur.right = next;
            }
            cur = cur.right;
        }
    }
}
